//
// Created by 啊汤哥 on 2025/9/10.
//
// 单链表

// 定义结构体

#include <stdexcept>
#include <stdlib.h>

typedef struct LNode {
    int data; //  数据域
    LNode *next; //  指针域

}LNode, *LinkList;

// 带头结点的初始化

bool InitList(LinkList &L) {
    // 在堆上创建一个新的链表节点
    // sizeof(LNode)：计算 LNode 结构体的大小（字节  malloc()：内存分配函数 (LNode*)：类型转换
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) {
        return false;
    }
    L->next = NULL;
    return true;

}

// 求链表的长度
int SingleLength(LinkList L) {
    int len = 0;
    //是创建一个临时指针变量 p，并将其初始化为指向链表的头节点 L
    LNode *p = L;
    while (p->next !=NULL) {
        p = p->next;
        len++;
    }
    return len;
}
// 按序号（位）查询
LNode *GetElem(LinkList L, int i) {
    if (i<1) return nullptr;
    LNode *p = L;
    int j = 0 ; // 记录当前指针的位置
    while (p!=nullptr && j<i) {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查询
LNode *LocateElement(LinkList L, int value) {
    LNode *p = L->next;
    while (p != NULL && p->data != value) {
        p = p->next;
    }
    // 找到直接返回该节点指针
    return p;
}

// 插入-- 指定位置插入 链表哪个位置 对应的值
bool LinkInsert(LinkList &L, int pos, int data) {
    // 先按位查找插入位置
    LNode *p = L;
    int j = 0; // 记录当前节点的位置

    // 这个是要找到那个位置
    while (p != NULL && j< pos-1) {
        p = p->next;
        j++;
    }
    //// 如果p为NULL，说明插入位置超过了链表长度
    if (p == nullptr) return false;
    // 分配新节点
    LNode *newNode =  (LNode*)malloc(sizeof(LNode));
    newNode->data = data;
    newNode->next = p->next;
    p->next = newNode;
    return true;
}

// 删除指定节点 -- 合法性 找到这个节点 删除 p->next指向下一个节点  -- 为什么data需要加& because要返回调用者
bool DeleteLinkNode(LinkList &L, int i, int &data) {
    if (i<1) return false;
    // 创建指针
    LNode *p = L;
    // 用来记录当前位置
    int j = 0;
    while (p->next != NULL && j < i-1) {
        p = p->next;
        j++;
    };
    // 如果找到了
    if (p->next != nullptr || j > i-1) {
        return false;
    }
    // 指向被删除的节点
    LNode *delNode = p->next;
    data = delNode->data;
    p->next = delNode->next;
    free(delNode);
    return true;

}